package backtracking;

import java.util.Random;

/**
 * MajorityElement
 *
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description:
 * @date 2021/5/19
 **/
public class MajorityElement {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {3, 2, 3};
        int majority = solution.majorityElement(nums);
        System.out.println(majority);
    }

    /**
     * 随机选取一个数，由于众数的数量总数量的一半，因此抽到的概率非常高 1/2
     */
    static class Solution {
        public int majorityElement(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            Random random = new Random();
            int majorityNum = nums[random.nextInt(nums.length)];
            while (!isMajorityElement(majorityNum, nums)) {
                majorityNum = nums[random.nextInt(nums.length)];
            }
            return majorityNum;
        }

        public boolean isMajorityElement(int majorityNum, int[] nums) {
            int count = 0, len = nums.length, i = 0;
            while (i < len) {
                if (nums[i] == majorityNum) count++;
                if (count > (len / 2)) return true;
                i++;
            }
            return false;
        }
    }

}
